/**
 * @file Student.h
 * @author Chensili <3190104816@zju.edu.cn>
 * @date Thur Oct 8 2020
 *
 * @brief Information of students.
 *
 *
 */

#ifndef _STUDENT_H_
#define _STUDENT_H_

class Student
{
 private:
  int std_no;  //Student number, every student has a unique number.
  char major;  //Student'major marked by one character, M for math,
               //P for Physics, C for Chemistry.
  double GPA;  //GPA range: 0 ~ 5.

 public:

  /**
   * Default construcor.
   *
   */
  Student();

  /**
   * Default construcor.
   *
   */
  Student(int _std_no, char _major, double _GPA);

  /**
   * Default construcor.
   *
   */
  ~Student();
  
  /**
   * Get the number of the student.
   *
   *
   * @return The number of the student.
   */
  int get_no();

  /**
   * Get the major of the student.
   *
   *
   * @return The major of the student.
   */
  char get_major();

  /**
   * Get the GPA  of the student.
   *
   *
   * @return The GPA of the student.
   */
  double get_GPA();

   /**
   * Change the number of the student.
   *
   *
   * @return  Error code, 0 for OK.
   */
  int change_std_no(int new_no);

  /**
   * Change the major of the student.
   *
   *
   * @return  Error code, 0 for OK.
   */
  char change_major(char new_major);

  /**
   * Change the GPA  of the student.
   *
   *
   * @return Error code, 0 for OK.
   */
  double change_GPA(double new_GPA);
  
  /**
   * Print out all elements.
   *
   *
   * @return  Error code, 0 for OK.
   */
  int printout();
};

class Heap
{
 private:
  Student *A;
  int n;

 public:
  #define PARENT(i) ((((i) + 1) >> 1) - 1)
  #define LEFTCHILD(i) (((i + 1) << 1) - 1)
  #define RIGHTCHILD(i) ((i + 1) << 1)

  /**
   * Default construcor.
   *
   */
  Heap();

  /**
   * Default construcor.
   *
   */
  Heap(Student *_A, int _n);

  /**
   * Get the pointer of the student.
   *
   *
   * @return The pointer to Student A.
   */
  Student* get_A();
  
   /**
   * Sort all elements in A by their major by heapsort method.
   *
   * @param A Pointer to the elements data.
   * @param n Total number of elements data.
   *
   * @return Error code, 0 for OK.
   */
  int sort_m();

   /**
   * Shift down the i-th element by major to build min-heap.
   *
   * @param i The index of the object in srting.
   *
   * @return Error code, 0 for OK.
   */
  int shiftdown(int i);
  
};

 /**
   * @brief Merge two sorted array to a sorted one.
   *
   * @param _A  Pointer to the elements data.
   * @param _p The index of the first element.
   * @param _q The index of the middle elemnet.
   * @param _r The index of the last element.
   *
   * @return Error code, 0 for OK.
   */
  int  Merge(Student *_A, int _p, int _q, int _r);

  /**
   * 
   * @brief Apply Merge Sort by Divide-and-Conquer method.
   *
   * @param _A  Pointer to the elements data.
   * @param _p The index of the first element.
   * @param _r The index of the last element.
   *
   * @return Error code, 0 for OK.
   */
  int Mergesort(Student *A, int _p, int _r);

  /**
   * A has been sorted by sort_m.
   * Sort all elements in A by their GPA  by mergesort method.
   *
   * @param A Pointer to the elements data.
   * @param begin_index The index of the first element for sorting.
   * @param end_index The index of the last element for sorting.
   *
   * @return Error code, 0 for OK.
   */
   int arrange(Student *A, int begin_index, int end_index);

#else
// Do nothing.
#endif





